package suanfa.linklist;

public class ResortLinkedlist {


    public static void main(String[] args) {
        int i=1;
        LNode head=new LNode();

        head.next=null;

        LNode tmp=null;

        LNode cur=head;

        //构造第一个链表
        for(;i<8;i++){
            tmp=new LNode();

            //tmp.data=1;
            tmp.data=i;

            tmp.next=null;

            cur.next=tmp;

            cur=tmp;


        }

        System.out.print("排序前： ");
        for(cur=head.next;cur!=null;cur=cur.next){
            System.out.print(cur.data+" ");
        }
        reorder(head);

        System.out.print("排序后： ");
        for(cur=head.next;cur!=null;cur=cur.next){
            System.out.print(cur.data+" ");
        }

    }

    private static LNode findMiddleNode(LNode head){
        if(head==null && head.next==null){
            return head;
        }

        LNode fast=head;
        LNode slow=head;
        LNode showPre=head;


        //当fast到链表尾时，slow恰好指向链表的中间节点
        while(fast!=null && fast.next!=null){
            showPre=slow;

            slow=slow.next;
            fast=fast.next.next;
        }

        //把链表断开成两个独立的子链表
        showPre.next=null;
        return slow;


    }

    private static LNode reverse(LNode head){
        if(head==null|| head.next==null){
            return head;
        }
        //前驱节点
        LNode pre=head;
        //当前节点
        LNode cur=head.next;
        //后继节点
        LNode next;

        pre.next=null;

        //使当前遍历到的节点cur指向其前驱节点
        while(cur!=null){
            next=cur.next;

            cur.next=pre;

            pre=cur;

            cur=cur.next;

            cur=next;


        }

        return pre;
    }

    private static void reorder(LNode head){
        if(head==null || head.next==null || head.next.next==null){
            return ;
        }

        LNode cur1=head.next;
        LNode mid=findMiddleNode(head.next);

        LNode cur2=reverse(mid);

        LNode tmp=null;

        //合并两个链表
        while(cur1.next!=null){
            tmp=cur1.next;

            cur1.next=cur2;

            cur1=tmp;

            tmp=cur2.next;

            cur2.next=cur1;

            cur2=tmp;

        }

        //cur2.next=cur2; 如果这行写成这样：结果会是这样：1 7 2 6 3，少了5,4
        cur1.next=cur2;
    }
}


